/**
 * 冒泡排序
 * 通过相邻元素之间的比较和交换，
 * 将最大（或最小）的元素逐步 “冒泡” 到序列的末尾（或开头）。
 * 具体来说，从序列的第一个元素开始，依次比较相邻的两个元素，如果它们的顺序不符合要求
 * （例如，在升序排序中，前一个元素大于后一个元素），则交换它们的位置。
 * 这样，每一轮比较都会将当前未排序部分的最大（或最小）元素移动到正确的位置上，
 * 就像气泡从水底逐渐上升到水面一样，所以被称为冒泡排序。
 * 步骤:
 * 比较相邻的元素。如果第一个比第二个大（升序排序），就交换它们的位置。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

/** 冒泡排序 */
function bubbleSort(arr) {
    const len = arr.length;
    let swapped;
    for (let i = 0; i < len; i++) {
        swapped = false;
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        // 如果在某一轮中没有发生交换，说明数组已经有序，可以提前结束排序
        if (!swapped) {
            break;
        }
    }
    return arr;
}

/**
 * 选择排序简述
 * 选择排序（Selection Sort）是一种简单直观的排序算法。
 * 它的基本思想是每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
 * 算法步骤
 * 初始化：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 * 遍历选择：从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 重复操作：重复第二步，直到所有元素均排序完毕。
 * 复杂度分析
 * 时间复杂度：无论数组初始状态如何，选择排序都需要进行两层嵌套循环，因此时间复杂度为 o(n*n)，其中 n 是数组的长度。
 * 空间复杂度：选择排序只需要常数级的额外空间，因此空间复杂度为 O(1)
 * @param {*} arr
 * @returns
 */
function selectionSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        // 假设当前索引对应的元素是最小值
        let minIndex = i;
        // 从 i+1 开始遍历剩余元素，找到最小值的索引
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 如果最小值的索引不是当前索引，交换它们
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

/*
 * 插入排序算法简述
 * 插入排序（Insertion Sort）是一种简单直观的排序算法，
 * 其基本思想是将未排序数据插入到已排序序列的合适位置，从而逐步构建有序序列。
 * 该算法在处理小规模数据或者数据基本有序的情况时表现出色。
 * 算法步骤
 * 初始状态：将数组的第一个元素视为已排序序列，其余元素视为未排序序列。
 * 选择元素：从未排序序列中取出一个元素，将其插入到已排序序列的合适位置。在插入过程中，需要将已排序序列中比该元素大的元素依次向后移动一位，为该元素腾出插入空间。
 * 重复操作：不断重复步骤 2，直到未排序序列中的所有元素都插入到已排序序列中。
 * 复杂度分析
 * 时间复杂度：在最坏情况下，数组完全逆序，插入排序需要进行 O(n * n)次比较和交换操作，其中 n 是数组的长度。
 * 在最好情况下，数组已经有序，插入排序只需要进行 O(n)次比较。
 * 空间复杂度：插入排序只需要常数级的额外空间，因此空间复杂度为 O(1)。
 */
function insertionSort(arr) {
    const len = arr.length;
    for (let i = 1; i < len; i++) {
        // 取出当前要插入的元素
        let current = arr[i];
        let j = i - 1;
        // 将比 current 大的元素依次向后移动
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 将 current 插入到合适的位置
        arr[j + 1] = current;
    }
    return arr;
}

// 测试用例
const arr1 = [64, 34, 25, 12, 22];
console.log('原始数组：', arr1);
const sortedArr1 = bubbleSort(arr1);
console.log('冒泡排序后的数组：', sortedArr1);

const arr2 = [64, 25, 12, 22, 11];
console.log('原始数组：', arr2);
const sortedArr2 = selectionSort(arr2);
console.log('选择排序后的数组：', sortedArr2);

const arr3 = [5, 3, 8, 4, 2];
console.log('原始数组：', arr3);
const sortedArr3 = insertionSort(arr3);
console.log('插入排序后的数组：', sortedArr3);
